#include <ctime>
#include <queue>
#include <map>
#include <set>
#include <list>
#include <iostream>
#include <cstring>
#include "MMU.h"

//Max base 10: 4294967295 
//Max base 16: FFFFFFFF

MMU::MMU(PageTable* ptable, TLB* t, MM* imm)
{
  // For Analysis
  TlbHitCount = 0;
  TlbMissCount = 0;
  PageInCount = 0;
  PageOutCount = 0;

  pt = ptable;
  tlbCopy = t;
  mm = imm;
}
void MMU::setTlb(TLB* t)
{
  tlbCopy = t;
}
int MMU::findAddress(bool read, int virtualAddress, int ibase, int ibound, int itick)
{
  int ret;
  int counter;
  int found;

  int page = virtualAddress >> OFFSET;
  cout << "    :: Page " << page << endl;

  // Look for page in TLB
  //check for it in tlb.
  int i=0;
  for(i = 0; i < K; i++)
  {
    if(tlbCopy->entries[i].page == page)
    {
      TlbHitCount++;
      cout << "Found in TLB. Frame: " << tlbCopy->entries[i].frame << endl;
      return 0;
    }
  }

  // TLB Missed!
  TlbMissCount++;

  // If there an empty slot in the PageTable then fill it
  // Else use replacement policy to make an empty slot, then fill it

  if(replacementPolicy == PG_LRUPURE)
  {
    LookupReturn pageTableRet = PTlookupLruPure(page,read,itick);
    int frameRet = -1;
    PraReturn praRet;
    switch (pageTableRet.ret) {
    case LOOKUP_REPLACE:
      praRet = LruPure();
      cout << "Frame Returned (Page Replaced): " << praRet.frame << endl;
      ret = insertNewPageLruPure(page,praRet.frame, itick, read);
      if (praRet.ret == PRA_CLEAN) 
      {
        cout << "Clean page removed" << endl;
        ret = PRA_CLEAN;
      }
      else 
      {
        cout << "Dirty page removed" << endl;
        ret = PRA_DIRTY;
      }
      break;	      
    case LOOKUP_INSERT:
      frameRet = FindOpeningsLruApprox(ibase, ibound);
      cout << "Frame Returned (Free space in MM): " << frameRet << endl;
      ret = insertNewPageLruPure(page,frameRet, itick, read);
      break;
    case LOOKUP_IN_MM:
    default:
      break;
    }

    if (pageTableRet.ret == LOOKUP_REPLACE ||
	pageTableRet.ret == LOOKUP_INSERT) {
      PageInCount++;
    }

    if (pageTableRet.ret == LOOKUP_REPLACE) {
      PageOutCount++;
    }

  }
  else if ( replacementPolicy == PG_LRUAPPROX)
  {
    int frameRet = -1;
    LookupReturn pageTableRet = PTlookupLruApprox(page);
    PraReturn praRet;
    switch (pageTableRet.ret) {
    case LOOKUP_REPLACE:
      praRet = LruApprox(itick);
      cout << "Frame Returned (Page Replaced): " << praRet.frame << endl;
      ret = insertNewPageLruApprox(page, praRet.frame, itick, read);
      if (praRet.ret == PRA_CLEAN) 
      {
        cout << "Clean page removed" << endl;
        ret = PRA_CLEAN;
      }
      else 
      {
        cout << "Dirty page removed" << endl;
        ret = PRA_DIRTY;
      }
      break;
    case LOOKUP_INSERT:
      frameRet = FindOpeningsLruApprox(ibase, ibound);
      cout << "Frame Returned (Free space in MM): " << frameRet << endl;
      ret = insertNewPageLruApprox(page, frameRet, itick, read);
      break;
    case LOOKUP_IN_MM:
    default:
      cout << "Found in MM" << endl;
      found = 0;

      // check if entry in tlb
      for(i = 0; i < K; i++)
      {
        if(tlbCopy->entries[i].page == page)
        {
          found = 1;
          break;
        }
      }
      // add if not in tlb
      if(found == 0){
         insertEntry(tlbCopy, itick, page, pt->entries[page].frame);
      }
      
      ret = 0; // Found address, no page fault
      break;
    }

    if (pageTableRet.ret == LOOKUP_REPLACE ||
	pageTableRet.ret == LOOKUP_INSERT) {
      PageInCount++;
    }

    if (pageTableRet.ret == LOOKUP_REPLACE) {
      PageOutCount++;
    }

  }
  else if ( replacementPolicy == PG_FIFO)
  {
    LookupReturn pageTableRet = PTlookupFIFO(page,read,itick);
    int frameRet = -1;
    PraReturn praRet;
    switch(pageTableRet.ret) {
    case LOOKUP_REPLACE:
      
      praRet = Fifo();
      cout << "Frame Returned (Replacing): " << praRet.frame << endl;
      ret = insertNewPageFIFO(page,praRet.frame, itick, read);
      if (praRet.ret == PRA_CLEAN) 
      {
        cout << "Clean page removed" << endl;
        ret = PRA_CLEAN;
      }
      else 
      {
        cout << "Dirty page removed" << endl;
        ret = PRA_DIRTY;
      }
      break;
    case LOOKUP_INSERT:
      frameRet = FindOpeningsLruApprox(ibase, ibound);
      cout << "Frame Returned (Free space in MM): " << frameRet << endl;
      ret = insertNewPageFIFO(page,frameRet, itick, read);
      break;

    case LOOKUP_IN_MM:
    
    default:
      break;
    }

    if (pageTableRet.ret == LOOKUP_REPLACE ||
	pageTableRet.ret == LOOKUP_INSERT) {
      PageInCount++;
    }

    if (pageTableRet.ret == LOOKUP_REPLACE) {
      PageOutCount++;
    }

  }
  else
  {
    // Periodically run cleaner for Working Set
    if (itick % 2 == 0) {
      cout << "    Cleaning" << endl;
      for (long i = 0; i < NUM_PAGES; i++) {
	// Page used && Ref ON => Set time to current tick
	if (pt->entries[i].frame != -1 && pt->entries[i].ref == 1) {
	  cout << "    " << i << ": New Time: " << itick << endl;
	  pt->entries[i].time = itick;
	  pt->entries[i].ref = 0;
	}
      }
    }

    LookupReturn pageTableRet = PTlookupWorkingSet(page,read,itick);
    int frameRet = -1;
    PraReturn praRet;
    switch (pageTableRet.ret) {
    case LOOKUP_REPLACE:
      praRet = WorkingSet(itick);
      ret = insertNewPageWorkingSet(page, praRet.frame, itick, read);

      if (praRet.ret == PRA_CLEAN) {
        cout << "Clean page removed" << endl;
        ret = PRA_CLEAN;
      } else {
        cout << "Dirty page removed" << endl;
        ret = PRA_DIRTY;
      }

      break;
    case LOOKUP_INSERT:
      frameRet = FindOpeningsLruApprox(ibase, ibound);
      ret = insertNewPageWorkingSet(page, frameRet, itick, read);

      ret = PRA_CLEAN;
      break;
    case LOOKUP_IN_MM:
    default:
      ret = 0;
      break;
    }

    if (pageTableRet.ret == LOOKUP_REPLACE ||
	pageTableRet.ret == LOOKUP_INSERT) {
      PageInCount++;
    }

    if (pageTableRet.ret == LOOKUP_REPLACE) {
      PageOutCount++;
    }

  }

  // print current page table
  cout << endl << "Page Table Entries:" << endl << 
  "Page\tFrame\tRef\tDirty\tTime" << endl << 
  "------------------------------------" << endl;
  for(counter = 0; counter < NUM_PAGES; counter++){
     if(pt->entries[counter].frame != -1){
        cout << counter << "\t" << 
        pt->entries[counter].frame << "\t" << 
        pt->entries[counter].ref << "\t" << 
        pt->entries[counter].dirty << "\t" << 
        pt->entries[counter].time << endl;
     }     
  }
  
  printTLB(tlbCopy);

  // print main memory
  cout << "MM:" << endl << "Frame\tValue" << endl << "-------------" << endl;
  for(counter = 0; counter < M; counter++){
     cout << counter << "\t" << mm->entries[counter].page << endl;
  }
  cout << endl;

  return ret;
}
void MMU::removeFromTlb(long page)
{
  cout << "Removing page " << page << endl;
  // Call after removing 
  int i =0;
  for(i = 0; i < K; i++)
  {
    if(tlbCopy->entries[i].page == page)
    {
      //remove that entry.
      tlbCopy->entries[i].page = -1;
      tlbCopy->entries[i].frame = -1;
    }
  }
}
// return frame value of opening, -1 if not found (shouldn't happen)
int MMU::FindOpeningsLruApprox(int ibase, int ibound){
     
   int mmCounter = -1;
   int memValue = -1;

   for(mmCounter = ibase; mmCounter <= ibound; mmCounter++) {
       if(mm->entries[mmCounter].page == -1){
           memValue = mmCounter; 
           break;           
       }
   }
   cout << "values:  from FindOpeningsLruApprox --- "<< ibase << " and " << ibound << endl;
    return memValue;
}
LookupReturn MMU::PTlookupLruPure(long page, bool read, int tick)
{
  cout << "LRU Pure" << endl;

  LookupReturn lookupRet;
//  lookupRet.ret = LOOKUP_IN_MM;
  
  //not in tlb. So look for it inside the page table
  if ( pt->entries[page].frame != -1)
  {
    //Found it! Set reference bit to 1
    pt->entries[page].ref = 1;
    pt->entries[page].time = tick;
    if (!read)
      pt->entries[page].dirty = 1;
    lookupRet.ret = LOOKUP_IN_MM;
    
    //insert into tlb
    insertEntry(tlbCopy,tick,page,pt->entries[page].frame);
  }
   // else return page fault
   else if(pt->numEntries < framesPerProcess){
      lookupRet.ret = LOOKUP_INSERT;
   }
   else{
      lookupRet.ret = LOOKUP_REPLACE;
   }  
  return lookupRet;
  
}

LookupReturn MMU::PTlookupWorkingSet(long page, bool read, int tick)
{
  LookupReturn lookupRet;
    //Found it! Set reference bit to 1
    // if entry in page table, return success
  if(pt->entries[page].frame != -1)
  {
    pt->entries[page].ref = 1;
    if (!read)
      pt->entries[page].dirty = 1;
    lookupRet.ret = LOOKUP_IN_MM;

    insertEntry(tlbCopy, tick, page, pt->entries[page].frame);
  }
   // else return page fault
   else if(pt->numEntries < framesPerProcess){
      lookupRet.ret = LOOKUP_INSERT;
   }
   else{
      lookupRet.ret = LOOKUP_REPLACE;
   }  
  return lookupRet;
}
 
LookupReturn MMU::PTlookupFIFO(long page, bool read, int tick)
{
  cout << "FIFO" << endl;

  LookupReturn lookupRet;
    //Found it! Set reference bit to 1
    // if entry in page table, return success
  if(pt->entries[page].frame != -1)
  {
    pt->entries[page].ref = 1;
    if (!read)
      pt->entries[page].dirty = 1;
    lookupRet.ret = LOOKUP_IN_MM;
    
    //insert into tlb
    insertEntry(tlbCopy,tick,page,pt->entries[page].frame);
  }
   // else return page fault
   else if(pt->numEntries < framesPerProcess){
      lookupRet.ret = LOOKUP_INSERT;
   }
   else{
      lookupRet.ret = LOOKUP_REPLACE;
   }  
  return lookupRet;
}
LookupReturn MMU::PTlookupLruApprox(long page)
{
  
   LookupReturn lookupRet;

   // if entry in page table, return success
   if(pt->entries[page].frame != -1){
      pt->entries[page].ref = 1;
      lookupRet.ret = LOOKUP_IN_MM;
   }
   // else return page fault
   else if(pt->numEntries < framesPerProcess){
      lookupRet.ret = LOOKUP_INSERT;
   }
   else{
      lookupRet.ret = LOOKUP_REPLACE;
   }
   return lookupRet;
}

int MMU::insertNewPageLruApprox(long page, int frame, int tick, bool read)
{

  cout << "Inserting - Page " << page << " | Frame " << frame << endl; 

  cout << "  Setting MM..." << endl;
  cout << "Frame = " << frame << endl;
  // Set MM
  mm->entries[frame].page = 1;

  cout << "  Setting PT..." << endl;
  // Set PageTable
  pt->entries[page].frame = frame;
  pt->entries[page].ref = 1;
  pt->entries[page].dirty = !read;
  pt->entries[page].time = -1;
  pt->numEntries++;

  // Add to TLB
  insertEntry(tlbCopy, tick, page, frame);

  cout << "NumEntries in Page Table: " << pt->numEntries << endl;

 return 1;
}
int MMU::insertNewPageWorkingSet(long page, int frame, int tick, bool read)
{
  cout << "Inserting - Page " << page << " | Frame " << frame << endl; 

  cout << "  Setting MM..." << endl;
  // Set MM
  mm->entries[frame].page = 1;

  cout << "  Setting PT..." << endl;
  // Set PageTable
  pt->entries[page].frame = frame;
  pt->entries[page].ref = 1;
  pt->entries[page].dirty = !read;
  pt->entries[page].time = -1;
  pt->numEntries++;

  // Add to TLB
  insertEntry(tlbCopy, tick, page, frame);

  return 1;
}
int MMU::insertNewPageFIFO(long page,int frame, int tick,bool read)
{
  cout<<"ADDING A NEW PAGE.. FRAME : "<<frame;
  
  mm->entries[frame].page = 1;
  pt->entries[page].frame = frame;
  pt->entries[page].time = tick;
  pt->entries[page].ref = 1;
  pt->numEntries++;
  
  //insert into tlb
  insertEntry(tlbCopy,tick,page,frame);
  //if its a write, set dirty bit
  if (!read)
    pt->entries[page].dirty = 1;
  else 
    pt->entries[page].dirty = 0;
  return 1;
}
int MMU::insertNewPageLruPure(long page,int frame, int tick,bool read)
{
  //return 0;
  mm->entries[frame].page = 1;
  pt->entries[page].frame = frame;
  pt->entries[page].time = tick;
  pt->entries[page].ref = 1;
  pt->numEntries++;
  //insert into tlb
  insertEntry(tlbCopy,tick,page,frame);
  //if its a write, set dirty bit
  if (!read)
    pt->entries[page].dirty = 1;
  else 
    pt->entries[page].dirty = 0;
  return 1;

}
PraReturn MMU::LruPure()
{
  //int page = virtualAddress >> OFFSET;
  //int offset = virtualAddress % OFFSET;
  int i = 0;
     
   //***************LRU - PRA: START***************
   //else : find the frame to throw out.
   int lruIndex = 0, lruTime = 0;
   for (i = 0; i < 1048576; i++)
   {
     if (pt->entries[i].frame != -1)
     {
       lruTime = pt->entries[i].time;
       lruIndex = i;
       break;
     }
   }   
   for(i = 0; i < 1048576; i++)
   {
     if (pt->entries[i].frame!=-1 && pt->entries[i].time < lruTime)
     {
       lruTime = pt->entries[i].time;
       lruIndex = i;
     }
   }
   pt->numEntries --;
   
   PraReturn praRet;
   praRet.frame = pt->entries[lruIndex].frame;
   pt->entries[lruIndex].frame = -1;
   mm->entries[praRet.frame].page = -1;
   praRet.ret = pt->entries[lruIndex].dirty? PRA_DIRTY: PRA_CLEAN;
   removeFromTlb(lruIndex);
  
   return praRet;
   //***************LRU - PRA: END***************
}
// removes frames with modified times less than the (current tick - gapThreshold)
// (unless all items above threshold then losest mod time selected)
// ADD: ** do something if dirty **
PraReturn MMU::LruApprox(int itick)
{
   int counter = 0;
   int done = 0;
   int chosenFrame = -1;
   int chosenPage = -1;
   int bestChoice = -1;
   PraReturn praRet;
   int i=0;
   for (i = 0; i < 1048576; i++)
   {
     if (pt->entries[i].frame != -1)
     {
       bestChoice = pt->entries[i].time;
       chosenPage = i;
       break;
     }
   }   
   for(counter = 0; counter < NUM_PAGES; counter++){
	      
       if((pt->entries[counter].frame != -1) && (pt->entries[counter].time < itick-gapThreshold)){
           chosenFrame = pt->entries[counter].frame;
           chosenPage = counter;
           done = 1;
           break;
       }
       if((pt->entries[counter].frame != -1) && (pt->entries[counter].time < bestChoice)){
	   chosenPage = counter;
       } 
   }

   if(done == 0 && chosenPage != -1){
       chosenFrame = pt->entries[chosenPage].frame;
   } 

  // Set return value to reflect whether removed page was dirty
  if (pt->entries[chosenPage].dirty == 1) {
    praRet.ret = PRA_DIRTY;
  } else {
    praRet.ret = PRA_CLEAN;
  }
 
  // Remove Page Table Entry
  pt->entries[chosenPage].frame = -1;
  pt->entries[chosenPage].ref = 0;
  pt->entries[chosenPage].dirty = 0;
  pt->entries[chosenPage].time = -1;
  pt->numEntries--;

  //    Remove from TLB
  removeFromTlb(chosenPage);

  //    Remove from MM
  mm->entries[chosenFrame].page = -1;

  praRet.frame = chosenFrame;
  
  cout << " RETURNING FRAME : "<< chosenFrame;


  return praRet;
}
PraReturn MMU::Fifo()
{
  //***************FIFO - PRA: START***************
   // find the frame to throw out.
   int i=0;
   int fifoIndex = 0, fifoTime = 0;
   for (i = 0; i < 1048576; i++)
   {
     if (pt->entries[i].frame != -1)
     {
       fifoTime = pt->entries[i].time;
       fifoIndex = i;
       break;
     }
   }
   for(i = 0; i < 1048576; i++)
   {
     if (pt->entries[i].frame!=-1 && pt->entries[i].time < fifoTime)
     {
       fifoTime = pt->entries[i].time;
       fifoIndex = i;
     }
   }
   pt->numEntries --;
   
   PraReturn praRet;
   praRet.frame = pt->entries[fifoIndex].frame;
   pt->entries[fifoIndex].frame = -1;   
   mm->entries[praRet.frame].page = -1;
   praRet.ret = pt->entries[fifoIndex].dirty? PRA_DIRTY: PRA_CLEAN;
   removeFromTlb(fifoIndex);
   return praRet;
   //***************FIFO - PRA: END***************
}
PraReturn MMU::WorkingSet(int itick)
{
  // Removes one page from page table according to
  // the working set page replacement algorithm.

  bool foundReplacement = false;
  int frame = -1;
  long page = -1;

  while (frame == -1) {
    cout << endl << "Page Table Entries2:" << endl << 
    "Page\tFrame\tRef\tDirty\tTime" << endl << 
    "------------------------------------" << endl;
    for(long counter = 0; counter < NUM_PAGES; counter++){
       if(pt->entries[counter].frame != -1){
          cout << counter << "\t" << 
          pt->entries[counter].frame << "\t" << 
          pt->entries[counter].ref << "\t" << 
          pt->entries[counter].dirty << "\t" << 
          pt->entries[counter].time << endl;
       }     
    }


    for (long i = 0; i < NUM_PAGES; i++) {

      if (pt->entries[i].frame != -1 && pt->entries[i].ref == 1) {
	cout << i << "|" << pt->entries[i].frame << "|Update tick" << endl;
	// Frame was used recently => Part of working set
	pt->entries[i].ref = 0;
	pt->entries[i].time = itick;

      } else if (!foundReplacement
		 && pt->entries[i].frame != -1 
		 && pt->entries[i].ref == 0
		 && itick - pt->entries[i].time > WS_TAU) {
	cout << i << "|" << pt->entries[i].frame << "|Not working set" << endl;
	// Frame is not in working set => Remove it.
	//    First save data
	frame = pt->entries[i].frame;
	page = i;
	foundReplacement = true;

      } else if (!foundReplacement
		 && pt->entries[i].frame != -1
		 && pt->entries[i].ref == 0
		 && itick - pt->entries[i].time <= WS_TAU) {
	cout << i << "|" << pt->entries[i].frame << "|Working set";
	// Frame is in working set => spare it unless nothing outside working set
	if (frame == -1) {
	  cout << "|Keep(1st)" << endl;
	  // First working set frame => save it
	  frame = pt->entries[i].frame;
	  page = i;
	} else { //frame != -1
	  // Not first working set frame =>
	  //    Keep oldest frame (hack to previous oldest page)
	  if (pt->entries[i].time < pt->entries[page].time) {
	    cout << "|Keep(older)";
	    // Newly found frame is older
	    frame = pt->entries[i].frame;
	    page = i;
	  }
	  cout << endl;
	}
      }
    }
  }

  cout << "Removing frame " << frame << endl;

  PraReturn praRet;
  praRet.frame = frame;

  // Set return value to reflect whether removed page was dirty
  if (pt->entries[page].dirty == 1) {
    praRet.ret = PRA_DIRTY;
  } else {
    praRet.ret = PRA_CLEAN;
  }

  //    Remove from PageTable
  pt->entries[page].frame = -1;
  pt->entries[page].ref = 0;
  pt->entries[page].dirty = 0;
  pt->entries[page].time = -1;
  pt->numEntries--;

  //    Remove from TLB
  removeFromTlb(page);

  //    Remove from MM
  mm->entries[frame].page = -1;

  return praRet;
}

void MMU::daemon(int ptick, int tick)
{
  cout << "DAEMON" << endl;

  int F = getFramesPerProcess();
  if ( pt->numEntries >= F)
    {
      cout << "  Removing " << G << " entries" << endl;

      int i=0;
      if (replacementPolicy == PG_LRUPURE)
	{
	  for ( i=0; i < G; i++)
	    {
	      if (pt->numEntries == 0)
	        break;
	      LruPure();
	    } 
	}
      else if ( replacementPolicy == PG_LRUAPPROX)
	{
	  for ( i=0; i < G; i++)
	    {
	      if (pt->numEntries == 0)
	        break;
	      LruApprox(tick);
	    }
	}
      else if ( replacementPolicy == PG_FIFO)
	{
	  for ( i=0; i < G; i++)
	    {
	      if (pt->numEntries == 0)
	        break;
	      Fifo();
	    } 
    
	}
      else if ( replacementPolicy == PG_WORKINGSET)
	{
	  for ( i=0; i < G; i++)
	    {
	      if (pt->numEntries == 0)
	        break;
	      WorkingSet(ptick);
	      // print current page table
	      cout << endl << "Page Table Entries:" << endl << 
		"Page\tFrame\tRef\tDirty\tTime" << endl << 
		"------------------------------------" << endl;
	      for(long counter = 0; counter < NUM_PAGES; counter++){
          if(pt->entries[counter].frame != -1){
            cout << counter << "\t" << 
            pt->entries[counter].frame << "\t" << 
            pt->entries[counter].ref << "\t" << 
            pt->entries[counter].dirty << "\t" << 
            pt->entries[counter].time << endl;
          }     
        }
      }
    }
  } else {
    cout << "  Not removing entries" << endl;
  }
  
  // print main memory
  int counter=0;
  cout << "MM after DAEMON:" << endl << "Frame\tValue" << endl << "-------------" << endl;
  for(counter = 0; counter < M; counter++){
     cout << counter << "\t" << mm->entries[counter].page << endl;
  }
  cout << endl;
}
